package Collection.JavaSet;

//HashSet底层原理
//HashSet集合底层采取哈希表存储数据
//哈希表是一种对于增删查改数据性能都比较好的数据结构,在JDK8以前由数组+链表组成,在JDK8以后由数组+链表+红黑树组成(底层数据结构)

public class JavaHashSet {
    //哈希值 int index = (数组长度 - 1) & 哈希值
    //哈希值是根据hashCode方法算出来的int类型的整数,该方法定义在Object类中,所有对象均可调用,默认使用地址值进行计算
    //所以一般情况下会重写hashCode方法,利用对象内部的属性值计算哈希值
    public static void main(String[] args) {
        //对象的哈希值特点
        //1.如果没有重写hashCode()方法,不同对象计算出的哈希值是不同的
        Student s1 = new Student("zhangsan", 21);
        Student s2 = new Student("zhangsan", 22);
        //2.如果已经重写hashCode()方法,不同的对象只要属性值相同,计算出的哈希值就是一样的
        //3.在小部分情况下,不同的属性值或者不同的地址值计算出来的哈希值也有可能一样(哈希碰撞/哈希冲突)

        //HashSet底层原理
        //1.创建一个默认长度16,默认加载因子为0.75的数组,数组名为table
        //2.根据元素的哈希值跟数组的长度计算出应存入的位置 index = (数组长度 - 1) & 哈希值
        //3.根据当前位置是否为null,如果是null直接存入,如果不是null表示有元素,则调用equals()方法比较属性值,一样不存(Set的互异性),不一样会存入数组,形成链表(添加元素的过程)
        //4.在JDK8以前新元素存入数组时老元素会挂在新元素下面,在JDK8以后新元素会直接挂在老元素下面

        //在JDK8以后如果链表长度超过8并且数组长度大于等于64时链表会自动转换为红黑树
        //如果集合中存储的是自定义对象,必须要重写hashCode()方法和equals()方法

        //为什么HashSet存和取的顺序不一样? 因为底层结构的数组中还会含有链表或红黑树,链表和红黑树也是需要遍历的,并且由于新老元素的存储顺序不同可能也会导致HashSet存和取的顺序不同
        //为什么HashSet没有索引? 因为底层数据结构中含有链表和红黑树,此时再给出索引的定义会比较模糊和争议
        //HashSet利用什么方法对数据进行去重? 通过hashCode()方法和equals()方法
    }
}

